import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-17
 * Time: 20:54
 */
public class Solution {
    //记录一门课程都是哪些课程的先修课程
    public ArrayList<ArrayList<Integer>> lists=new ArrayList<>();
    public int[] arr;//记录一个课程依赖的课程数
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        this.arr=new int[numCourses];
        int count=0;//记录能修完的课程数目

        for(int i=0;i<numCourses;i++){
            ArrayList<Integer> list=new ArrayList<>();
            lists.add(list);
        }

        for(int[] t:prerequisites){
            lists.get(t[1]).add(t[0]);//记录这门课都是哪些课程的先修课程
            arr[t[0]]++;//记录这门课程的先修课程数
        }

        Queue<Integer> queue=new LinkedList<>();
        for(int i=0;i<arr.length;i++){
            if(arr[i]==0){
                //这门课没有先修课程就添加到队列中
                //下标就代表这门课
                queue.offer(i);
                count++;
            }
        }

        //广度优先遍历
        while(!queue.isEmpty()){
            int out=queue.poll();
            ArrayList<Integer> temp=lists.get(out);
            //将所有依赖这门课程的依赖课程数目都-1
            for(Integer index:temp){
                arr[index]--;;
                if(arr[index]==0){
                    //如果某一门课程依赖数目为0,就添加到队列中
                    queue.offer(index);
                    count++;
                }
            }
        }
        return count==numCourses;
    }
}
